package org.xingole.leetcode.dp;

import java.util.Arrays;
import java.util.Scanner;

public class StudentAttendanceRecordII {
    private static final int MOD = (int) 1e9 + 7;

    public int checkRecord(int n) {
        /*
         * dp[i][j][k] is defined as the number of rewarding attendance records 
         * that have j 'A's in the previous i days and k consecutive 'L's 
         * at the end, where 0 <= i <= n, 0 <= j <= 1, and 0 <= k <= 2.
         */
        int[][][] dp = new int[n + 1][2][3];

        // base cases
        dp[0][0][0] = 1;

        for (int i = 1; i <= n; i++) {

            // the number ending with 'P'
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 2; k++) {
                    dp[i][j][0] = (dp[i][j][0] + dp[i-1][j][k]) % MOD;
                }
            }

            // the number ending with 'A'
            for (int k = 0; k <= 2; k++) {
                dp[i][1][0] =(dp[i][1][0] + dp[i - 1][0][k]) % MOD;
            }

            // the number ending with 'L'
            for (int j = 0; j <= 1; j++) {
                for (int k = 1; k <= 2; k++) {
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD;
                }
            }

        }

        int sum = 0;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                sum = (sum + dp[n][j][k]) % MOD;
            }
        }

        return sum;
    }

    public int checkRecord2(int n) {
        int[][] dp = new int[2][3];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int[][] dpNew = new int[2][3];

            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 2; k++) {
                    dpNew[j][0] = (dpNew[j][0] + dp[j][k]) % MOD;
                }
            }

            for (int k = 0; k <= 2; k++) {
                dpNew[1][0] = (dpNew[1][0] + dp[0][k]) % MOD;
            }

            for (int j = 0; j <= 1; j++) {
                for (int k = 1; k <= 2; k++) {
                    dpNew[j][k] = (dpNew[j][k] + dp[j][k - 1]) % MOD;
                }
            }

            dp = dpNew;
        }

        int sum = 0;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                sum = (sum + dp[j][k]) % MOD;
            }
        }

        return sum;
    }

    /**
     * We can use the fast exponentiation of matrices to solve it. It can reduce
     * the time complexity from O(n) to O(log n).
     * 
     * <p>
     * To use matrix fast exponentiation, it is necessary to merge j and k in the
     * dynamic programming representation of method 1 into one dimension, that is,
     * the state of dynamic programming is: dp[i][j*3+k] represents the number of
     * rewarding attendance records that have j 'A's in the previous i days and k
     * consecutive 'L's at the end, where 0 <= i <= n, 0 <= j <= 1, 0 <= k <= 2, and
     * 0 <= j*3+k < 6.
     * 
     * <p>
     * Under the new dynamic programming state definition, the boudary case is
     * dp[0][0] = 1. When 1 <= i <= n, the state transition equation is as follows:
     * 
     *         dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] <br/>
     *         dp[i][1] = dp[i-1][0] <br />
     *         dp[i][2] = dp[i-1][1] <br />
     *         dp[i][3] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4] + dp[i-1][5] <br />
     *         dp[i][4] = dp[i-1][3] <br />
     *         dp[i][5] = dp[i-1][4] <br />
     * 
     * Let dp[n] represent a row vector containing 6 elements:
     * 
     *         dp[n] = (d[n][0], dp[n][1], dp[n][2], dp[n][3], dp[n][4], dp[n][5])
     * 
     * We can construct such a recurrence relation:
     *         dp[n] = dp[n-1] * mat.
     */
    public int checkRecord3(int n) {
        long[][] mat = {{1, 1, 0, 1, 0, 0},
                        {1, 0, 1, 1, 0, 0},
                        {1, 0, 0, 1, 0, 0},
                        {0, 0, 0, 1, 1, 0},
                        {0, 0, 0, 1, 0, 1},
                        {0, 0, 0, 1, 0, 0}};
        long[][] res = pow(mat, n);
        long sum = Arrays.stream(res[0]).sum();
        return (int) (sum % MOD);
    }

    private long[][] pow(long[][] mat, int n) {
        long[][] ret = {{1, 0, 0, 0, 0, 0}}; // dp[0]
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, mat);
            }
            n >>= 1;
            mat = multiply(mat, mat);
        }
        return ret;
    }

    public long[][] multiply(long[][] a, long[][] b) {
        int rows = a.length, columns = b[0].length, temp = b.length;
        long[][] c = new long[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                for (int k = 0; k < temp; k++) {
                    c[i][j] += a[i][k] * b[k][j];
                    c[i][j] %= MOD;
                }
            }
        }
        return c;
    }

    public static void main(String[] args) {
        var sar2 = new StudentAttendanceRecordII();

        try (var scanner = new Scanner(System.in)) {
            int n = scanner.nextInt();

            System.out.println(sar2.checkRecord(n));
        }
    }
}
